Euclidean Clustering

Once the KD-Tree method for searching for nearby points is implemented, its not difficult to implement a euclidean clustering method that groups individual cluster indices based on their proximity. Inside cluster.cpp there is a function called euclideanCluster which returns a vector of vector ints, this is the list of cluster indices.

To perform the clustering, iterate through each point in the cloud and keep track of which points have been processed already. For each point add it to a list of points defined as a cluster, then get a list of all the points in close proximity to that point by using the search function from the previous exercise. For each point in close proximity that hasn't already been processed, add it to the cluster and repeat the process of calling proximity points. Once the recursion stops for the first cluster, create a new cluster and move through the point list, repeating the above process for the new cluster. Once all the points have been processed, there will be a certain number of clusters found, return as a list of clusters.

Pseudocode

Proximity(point,cluster):
    mark point as processed
    add point to cluster
    nearby points = tree(point)
    Iterate through each nearby point
        If point has not been processed
            Proximity(cluster)

EuclideanCluster():
    list of clusters 
    Iterate through each point
        If point has not been processed
            Create cluster
            Proximity(point, cluster)
            cluster add clusters
    return clusters

The EuclideanCluster is called in cluster.cpp line 123:

std::vector<std::vector<int>> clusters = euclideanCluster(points, tree, 3.0);

The image below shows the expected output results.

Instructions

• In src/quiz/cluster/cluster.cpp fill in the euclideanCluster function.

• Once the method is working for the 2D point example, try extending it to work with 3D point clouds by doing the same logic but including the extra third dimension.

Compile/Run

• In src/quiz/cluster , mkdir build
• cd build
• cmake ..
• make
• ./quizCluster

Solution